Masala #0597

Xotira 20 MB Vaqt 1000 ms Qiyinchiligi 35 %

4.0 (Baholar 4)

Muallif: Shahzod

Labirintdagi yo'llar soni.

Sizga $N*M$ 0 va 1 lardan iborat labirint beriladi. labirintda eshigi ochiq(0) va yopiq(1) xonalar mavjud.

Bu labirintda siz quyidagi amallarni bajarishngiz mumkin.

1.Labirintning satrdagi keyingi eshigi ochiq bo'lgan xonaga o'tishingiz mumkin.

2.Labirintning ustunidagi keyingi eshigi ochiq bo'lgan xonaga o'tishingiz mumkin.

Ushbu amallarni bajargan holda labirintning $(1,1)$ xonasidan $(N,M)$ xonasiga borishning usullar soni hisoblang.

Kiruvchi ma'lumotlar:

1-qatorda $N$ va $M$ $(1 \le N,M \le 1000)$ .

$N$ ta ustunda xonalardan iborat uzunligi $M$ ga teng satrlar.

Chiquvchi ma'lumotlar:

$(N,M)$ xonaga borish usullar sonini $10^9+7$ ga bo'lgandagi qoldiq.

Misollar

#	input.txt	output.txt
1	3 3 000 011 000	3

Izoh:

000
011
000 bu labirint uchun yo'llar soni.

$1. (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3)$

$2. (1,1) -> (1,2) -> (3,2) -> (3,3)$

$3. (1,1) -> (1,2) -> (1,3) -> (3,3)$

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin